package xyz.naokeziteng.data_structure.hash;

/**
 * @author hawk
 * @date 2022/9/29
 * @desc 自定义hash表
 **/
public class HashTable<K, V> {
    //初始容量
    private static final int INIT_CAPACITY = 16;
    //最大容量
    private static final int MAXIMUM_CAPACITY = 1 << 30;

    //数据数组
    private Object[] data;
    //元素个数
    private int size;

    public HashTable() {
        data = new Object[INIT_CAPACITY];
        size = 0;
    }

    public HashTable(int capacity) {
        data = new Object[tableSizeFor(capacity)];
        size = 0;
    }

    public int getSize() {
        return this.size;
    }

    public boolean isEmpty() {
        return this.size == 0;
    }


    //返回大于cap的最小的2的n次幂
    private int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }


    //链表节点类
    private class Node<K, V> {
        private K key;
        private V value;
        private Node next;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.next = null;
        }
    }


}
